/**
 * @author ZhiWen Ren
 * @version 1.0
 * @description: Solution-74-搜索二维矩阵
 * @date 2025/5/20 10:03
 */
public class Solution74 {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rowIndex = binarySearchFirstRow(matrix, target);
        if (rowIndex == -3) {
            return false;
        }
        if (rowIndex == -2) {
            return true;
        }
        if (rowIndex == -1) {
            rowIndex++;
        }
        return findTarget(matrix[rowIndex], target);
    }

    private int binarySearchFirstRow(int[][] matrix, int target) {
        // 给定一个严格递增的数组和一个target，找到这个数组中下标尽可能大且元素值不超过target的元素下标
        if (matrix[0][0] > target) {
            // [0][0]元素都比target大
            return -3;
        }
        int low = 0;
        int high = matrix.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (matrix[mid][0] > target) {
                high = mid - 1;
            } else if (matrix[mid][0] < target) {
                low = mid + 1;
            } else {
                // 找到了target
                return -2;
            }
        }
        //找到这个数组中下标尽可能大且元素值不超过target的元素下标
        return low - 1;
    }

    private boolean findTarget(int[] row, int target) {
        int left = 0;
        int right = row.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (row[mid] == target) {
                return true;
            } else if (row[mid] > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return false;
    }
}
